Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Optimal coalition structure generation in monotonous overlapping coalition
GUO Zhipeng, LIU Jinglei
Journal of Computer Applications    2021, 41 (1): 103-111.   DOI: 10.11772/j.issn.1001-9081.2020060973
Abstract265)      PDF (1073KB)(396)       Save
Aiming at the problem that Overlapping Coalition Structure Generation (OCSG) in the Framework of cooperative games with Overlapping Coalitions (OCF games) is difficult to solve, an effective algorithm based on greedy method was proposed. First, the OCF games with number of coalition k constraints (kOCF games) was used to limit the scale of the OCSG problem. Then, a similarity measure was introduced to represent the similarity between any two coalition structures, and the property of monotonicity was defined based on the similarity measure, which means that the higher the similarity between a coalition structure and optimal coalition structure, the greater the monotonicity value of this coalition. Finally, for the kOCF games with monotonicity, the method of inserting player numbers one by one to approximate the optimal coalition structure was used to design the Coalition Constraints Greed (CCG) algorithm to solve the given OCSG problem, and the complexity of CCG algorithm was proved to be O( n2 k+1) theoretically. The influences of different parameters and coalition value distribution on the performance of the proposed algorithm were analyzed and verified through experiments, and this algorithm was compared with the algorithm proposed by Zick et al. (ZICK Y, CHALKIADAKIS G, ELKIND E, et al. Cooperative games with overlapping coalitions:charting the tractability frontier. Artificial Intelligence, 2019, 271:74-97) in the terms such as constraint condition. The results show that when the maximum number of coalitions k is constrained by a constant, the search times of the proposed algorithm increase linearly with the number of agents. It can be seen that CCG algorithm is tractable with the fixed-parameter k and has better applicability.
Reference | Related Articles | Metrics